class Node {
  constructor(key){
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

/**
 *
 * insert(key)：向树中插入一个新的键。
 * search(key)：在树中查找一个键。如果节点存在，则返回 true；如果不存在，则返回false。
 * inOrderTraverse()：通过中序遍历方式遍历所有节点。
 * preOrderTraverse()：通过先序遍历方式遍历所有节点。
 * postOrderTraverse()：通过后序遍历方式遍历所有节点。
 * min()：返回树中最小的值/键。
 * max()：返回树中最大的值/键。
 * remove(key)：从树中移除某个键。
 *
 * @class BinarySearchTree  BST
 * 二叉搜索树（BST）是二叉树的一种，但是只允许你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大的值
 */
class BinarySearchTree {
  constructor() { 
    this.root = null; // Node 类型的根节点
  }

  insert(key){
    if(this.root === null){
      this.root = new Node(key);
    }else{
      this.insertNode(this.root, key);
    }
  }
  insertNode(node, key){
    if(key < node.key){
      if(node.left === null){
        node.left = new Node(key);
      }else{
        this.insertNode(node.left, key);
      }
    }else{
      if(node.right === null){
        node.right = new Node(key);
      }else{
        this.insertNode(node.right, key);
      }
    }
  }

  // 中序遍历：一定是按照从小到大的顺序输出的 左-》中-》右
  // 中序遍历是一种以上行顺序访问 BST 所有节点的遍历方式，也就是以从最小到最大的顺序访问所有节点。
  inOrderTraverse(callback) { 
    this.inOrderTraverseNode(this.root, callback);
  }
  inOrderTraverseNode(node, callback){
    if(node !== null){
      this.inOrderTraverseNode(node.left, callback);
      callback(node.key)
      this.inOrderTraverseNode(node.right, callback);
    }
  }

  // 先序遍历：中-》左-》右 可以确定根节点
  // 先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。
  preOrderTraverse(callback) { 
    this.preOrderTraverseNode(this.root, callback); 
  }
  preOrderTraverseNode(node, callback) { 
    if (node != null) { 
      callback(node.key);
      this.preOrderTraverseNode(node.left, callback);
      this.preOrderTraverseNode(node.right, callback);
    } 
  }

  // 后序遍历：左-》右-》中 
  // 后序遍历则是先访问节点的后代节点，再访问节点本身。后序遍历的一种应用是计算一个目录及其子目录中所有文件所占空间的大小
  postOrderTraverse(callback) { 
    this.postOrderTraverseNode(this.root, callback); 
  }
  postOrderTraverseNode(node, callback) { 
    if (node != null) { 
      this.postOrderTraverseNode(node.left, callback);
      this.postOrderTraverseNode(node.right, callback);
      callback(node.key);
    } 
  }

  // 最小值
  min(){
    return this.minNode(this.root);
  }
  minNode(node) { 
    let current = node; 
    while (current != null && current.left != null) {
      current = current.left;
    } 
    return current;
  }

  // 最大值
  max(){
    return this.maxNode(this.root);
  }
  maxNode(node) { 
    let current = node; 
    while (current != null && current.right != null) {
      current = current.right;
    } 
    return current;
  }

  // 搜索一个特定的值
  search(key) { 
    return this.searchNode(this.root, key);
  }
  searchNode(node, key){
    if (node == null) {
      return false; 
    }

    if(key < node.key){
      return this.searchNode(node.left, key);
    } else if (key > node.key){
      return this.searchNode(node.right, key);
    } else {
      return true;
    }
  }

  // 移除一个节点
  remove(key) { 
    this.root = this.removeNode(this.root, key);
  }
  removeNode(node, key) {
    if (node == null) {
      return false; 
    }

    if(key < node.key){
      node.left = this.removeNode(node.left, key);
      return node;
    } else if (key > node.key){
      node.right = this.removeNode(node.right, key);
      return node;
    } else {
      // 第一种情况：没有子节点，直接设置为null
      if (node.left == null && node.right == null) {
        node = null;
        return node;
      }

      // 第二种情况：有一个子节点，就直接指向它子节点
      if (node.left == null) {
        node = node.right;
        return node;
      } else if (node.right == null) {
        node = node.left;
        return node;
      }

      // 第三种情况：有两个子节点,找到右侧最小的指向它，然后在删掉它
      const aux = this.minNode(node.right);
      node.key = aux.key;
      node.right = this.removeNode(node.right, aux.key);
      return node;
    }
  }
}


/* const tree = new BinarySearchTree(); 
tree.insert(11);
tree.insert(7); 
tree.insert(15); 
tree.insert(5); 
tree.insert(3); 
tree.insert(9); 
tree.insert(8); 
tree.insert(10); 
tree.insert(13); 
tree.insert(12); 
tree.insert(14); 
tree.insert(20); 
tree.insert(18); 
tree.insert(25);
tree.insert(6);

const printNode = (value) => console.log(value);

// 中序遍历
tree.inOrderTraverse(printNode);
// 先序遍历
tree.preOrderTraverse(printNode);
// 后序遍历
tree.postOrderTraverse(printNode);

console.log(tree.max(), tree.min());

console.log(tree.search(1) ? 'Key 1 found.' : 'Key 1 not found.'); 
console.log(tree.search(8) ? 'Key 8 found.' : 'Key 8 not found.'); */


// AVL树 = 平衡树 + 二叉排序树
/**
 * 
 * @class AVLTree AVL 树是一种自平衡二叉搜索树，意思是任何一个节点左右两侧子树的高度之差最多为 1
 * @extends {BinarySearchTree}
 */
class AVLTree extends BinarySearchTree {
  constructor(){
    super();
    this.root = null;
  }

  // 计算一个节点高度：
  // 可以设置子节点为空的高度为-1，然后在比较左右节点的高度，取最大的然后 +1，这样就可以实现递归查寻高度
  getNodeHeight(node) {
    if(node === null){
      return -1;
    }
    return Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
  }

  // 平衡因子 = 左子树高度 - 右子树高度
  getBalance(node){
    return this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
  }

  // 左左（LL）：向右的单旋转
  // 这种情况出现于节点的左侧子节点的高度大于右侧子节点的高度时，并且左侧子节点也是平衡或左侧较重的
  rotationLL(node){
    const tmp = node.left;
    node.left = tmp.right;
    tmp.right = node;
    return tmp;
  }

  // 右右（RR）：向左的单旋转
  // 它出现于右侧子节点的高度大于左侧子节点的高度，并且右侧子节点也是平衡或右侧较重的
  rotationRR(node){
    const tmp = node.right;
    node.right = tmp.left;
    tmp.left = node;
    return tmp;
  }

  // 左右（LR）：向右的双旋转
  // 这种情况出现于左侧子节点的高度大于右侧子节点的高度，并且左侧子节点右侧较重
  rotationLR(node) { 
    node.left = this.rotationRR(node.left); 
    return this.rotationLL(node); 
  }

  // 右左（RL）：向左的双旋转
  // 这种情况出现于右侧子节点的高度大于左侧子节点的高度，并且右侧子节点左侧较重
  rotationRL(node) { 
    node.right = this.rotationLL(node.right); 
    return this.rotationRR(node);
  }
  
  insert(key) {
    this.root = this.insertNode(this.root, key); 
  }
  insertNode(node, key) {
    debugger
    // 像在 BST 树中一样插入节点
    if(node === null){
      return new Node(key);
    }else if(key < node.key){
      node.left = this.insertNode(node.left, key);
    }else if(key > node.key){
      node.right = this.insertNode(node.right, key);
    }else {
      return node; // 重复的键
    }
    
    // 如果需要，将树进行平衡操作
    const balance = this.getBalance(node);
    if(balance === 2){  // 需要平衡的节点在根节点左边
      if(key < node.left.key){ // 说明是 左左
        node = this.rotationLL(node);
      }else { // 左右 
        return this.rotationLR(node);
      }
    }

    if(balance === -2){  // 需要平衡的节点根节点右边
      if(key > node.right.key){ // 说明是 右右
        node = this.rotationRR(node);
      }else{ // 右左
        return this.rotationRL(node);
      }
    }
    return node;
  }

  remove(key) {
    this.root = this.removeNode(this.root, key); 
  }
  removeNode(node, key) {
    node = super.removeNode(node, key);
    if (node == null){
      return node; // null，不需要进行平衡
    }

    // 如果需要，将树进行平衡操作
    const balance = this.getBalance(node);
    if(balance === 2){  // 需要平衡的节点在根节点左边
      const balanceFactorLeft = this.getBalance(node.left);
      if(balanceFactorLeft === 0 || balanceFactorLeft === 1){
        return this.rotationLL(node);
      }
      if(balanceFactorLeft === -1){
        return this.rotationLR(node.left);
      }
    }

    if(balance === -2){  // 需要平衡的节点根节点右边
      const balanceFactorRight = this.getBalance(node.right);
      if(balanceFactorRight === 0 || balanceFactorRight === -1){
        return this.rotationRR(node)
      }
      if(balanceFactorRight === 1){
        return this.rotationRL(node.right);
      }
    }

    return node;
  }
}

// const tree = new AVLTree();
// tree.insert(50)
// tree.insert(30)
// tree.insert(70)
// tree.insert(10)
// tree.insert(40)
// tree.remove(70)
// console.log(tree)


class RedBlackNode extends Node { 
  constructor(key) { 
    super(key); 
    this.key = key; 
    this.color = 'RED';
    this.parent = null;
  } 

  isRed() { 
    return this.color === 'RED'; 
  } 
}

/**
 *  AVL 树一样，红黑树也是一个自平衡二叉搜索树。我们学习了对 AVL 书插入和移除节点
可能会造成旋转，所以我们需要一个包含多次插入和删除的自平衡树，红黑树是比较好的。如果
插入和删除频率较低（我们更需要多次进行搜索操作），那么 AVL 树比红黑树更好
 *
 * @class RedBlackTree 红黑树
 * @extends {BinarySearchTree}
 */
class RedBlackTree extends BinarySearchTree { 
  constructor() { 
    super(); 
    this.root = null; 
  } 

  rotationLL(node) { 
    const tmp = node.left;
    node.left = tmp.right; 
    if (tmp.right && tmp.right.key) { 
      tmp.right.parent = node;
    } 
    tmp.parent = node.parent; 
    if (!node.parent) { 
      this.root = tmp; 
    }else{ 
      if (node === node.parent.left) { 
        node.parent.left = tmp;
      } 
      else { 
        node.parent.right = tmp;
      } 
    } 
    tmp.right = node; 
    node.parent = tmp;
  }

  rotationRR(node) { 
    const tmp = node.right; 
    node.right = tmp.left; 
    if (tmp.left && tmp.left.key) { 
      tmp.left.parent = node;
    } 

    tmp.parent = node.parent; 
    if (!node.parent) { 
      this.root = tmp; 
    }else { 
      if (node === node.parent.left) { 
        node.parent.left = tmp;
      } 
      else { 
        node.parent.right = tmp;
      } 
    } 
    tmp.left = node; 
    node.parent = tmp; 
  }

  insert(key) { 
    if (this.root == null) {
      this.root = new RedBlackNode(key);
      this.root.color = 'BLACK';
    } else { 
      const newNode = this.insertNode(this.root, key);
      this.fixTreeProperties(newNode); // 验证红黑树规则
    } 
  }

  insertNode(node, key){
    if(key < node.key){
      if (node.left == null) { 
        node.left = new RedBlackNode(key); 
        node.left.parent = node;
        return node.left;
      }else{
        return this.insertNode(node.left, key);
      }
    }else if (node.right == null) { 
      node.right = new RedBlackNode(key); 
      node.right.parent = node;
      return node.right;
    } 
    else { 
      return this.insertNode(node.right, key); 
    }
  }

  fixTreeProperties(node) {
    while (node && node.parent && node.parent.color.isRed()
    && node.color !== 'BLACK') {
      let parent = node.parent;
      const grandParent = parent.parent;
      
      // 情形 A：父节点是左侧子节点
      if (grandParent && grandParent.left === parent) {
        const uncle = grandParent.right;

        // 情形 1A：叔节点也是红色——只需要重新填色
        if (uncle && uncle.color === 'RED') {
          grandParent.color = 'RED'; 
          parent.color = 'BLACK'; 
          uncle.color = 'BLACK'; 
          node = grandParent;
        }else{
          // 情形 2A：节点是右侧子节点——左旋转
          if (node === parent.right) { 
            this.rotationRR(parent);
            node = parent;
            parent = node.parent;
          }
          // 情形 3A：节点是左侧子节点——右旋转
          this.rotationLL(grandParent);
          parent.color = 'BLACK';
          grandParent.color = 'RED';
          node = parent;
        }
      }else{ // 情形 B：父节点是右侧子节点
        const uncle = grandParent.left;
        // 情形 1B：叔节点是红色——只需要重新填色
        if (uncle && uncle.color === 'RED') {
          grandParent.color = 'RED'; 
          parent.color = 'BLACK'; 
          uncle.color = 'BLACK'; 
          node = grandParent; 
        } 
        else { 
          // 情形 2B：节点是左侧子节点——左旋转
          if (node === parent.left) { 
            this.rotationLL(parent);
            node = parent; 
            parent = node.parent; 
          } 
          // 情形 3B：节点是右侧子节点——左旋转
          this.rotationRR(grandParent);
          parent.color = 'BLACK'; 
          grandParent.color = 'RED'; 
          node = parent;
        } 
      }
    }
    this.root.color = 'BLACK';
  }
}

const tree = new RedBlackTree();
console.log(tree)